package 极客算法训练营.chapter03;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 *
 * 示例 1：
 *
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 */

public class 爬楼梯 {
    public static void main(String[] args) {
//        System.out.println(climbStairs(3));
        System.out.println(climbStairs2(5));
    }


    /**
     * fn = f(n-1) + f(n-2)
     * @param n
     * @return
     */
    public static int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public static int climbStairs2(int n) {
        //防止越界
        int[] memo = new int[n + 1];
        return climbMemo(n, memo);
    }

    public static int climbMemo(int n, int[] memo) {
        //递归终止条件
        if (n == 0 || n == 1) {
            //添加缓存
            memo[n] = 1;
        }
        //判断是否有缓存结果
        if (memo[n] > 0) {
            return memo[n];
        } else {
            memo[n] = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
        }
        return memo[n];
    }

    public static int climnStairs3(int n) {
        //边界条件
        if (n == 0 || n == 1) {
            return 1;
        }
        //从第二阶开始。第一次循环中，q代表n=0，r代表n=1这两个初始值，r(2)=f(0)+f(1)
        int p = 0, q = 1, r = 1;
        for (int i = 2; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}
